/**
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

示例 1:

输入: k = 5

输出: 9


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/get-kth-magic-number-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func getKthMagicNumber(k int) int {
	ugly := -1
	myH := myHeap{}
	heap.Init(&myH)
	heap.Push(&myH, 1)
	for i := 0; i < k; i ++ {
		for myH[0] == ugly{
			heap.Pop(&myH)
		}
		ugly = heap.Pop(&myH).(int)
		heap.Push(&myH, 3*ugly)
		heap.Push(&myH, 5*ugly)
		heap.Push(&myH, 7*ugly)
	}
	return ugly
}

type myHeap []int

func (h myHeap)Len() int  {
	return len(h)
}

func (h myHeap)Less(i, j int) bool  {
	return h[i] < h[j]
}

func (h myHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
	return
}

func (h *myHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *myHeap) Pop() interface{} {
	res := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return res
}